package tree;

/**
 * @author justnow
 * Created on 2020-10-04
 * Description
 * 二叉搜索树的最近公共祖先
 */
public class SwardOffer68_1 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            //情况一，若root.val小于p的val和q的val，那么就说明其最近的公共祖先节点在右子树上
            if (root.val < p.val && root.val < q.val) {
                root = root.right;
            //情况二，若root.val大于p的val和q的val，那么就说明其最近的公共祖先节点在左子树上
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;
            // 情况三，也就是root.val介于p的val和q的val之间，那么说明root就是最近的公共祖先节点。
            } else {
                break;
            }
        }
        return root;
    }
}
